Skip to content

Leetcode 72. Edit Distance 题解

题目链接

Leetcode 72. Edit Distance

题目内容

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

解题思路

本周继续我们的DP之旅，对于这周这种题目，基本第一时间可以想到的就是我们的一个O(mn)的一个算法， 我们令dp[i][j]为word1.substr(0, i)和word2.substr(0, j)之间的编辑距离，那么我们有以下的状态转移方程

dp[i][j] = 0 if (i == 0 or j == 0)

dp[i][j] = dp[i-1][j-1] if (word1[i - 1] == word2[j-1])

dp[i][j] = min(dp[i-1]j, dp[i]j-1, dp[i-1]j-1) + 1

这种方法做出来的结果时间复杂度就是O(mn)，detail提交结果如下: result

题目代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 0; i <= m; i++)
            dp[i][0] = i;
        for(int j = 0; j <= n; j++)
            dp[0][j] = j;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(word1[i - 1] == word2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                } else{
                    int deleteAction = dp[i - 1][j];
                    int insert = dp[i][j - 1];
                    int replace = dp[i - 1][j - 1];
                    dp[i][j] = min(deleteAction, min(insert, replace)) + 1;
                }
            }
        }
        return dp[m][n];
    }
};